
fn getMax a b =
(
	if(a > b) then
		return a;
	
	return b;
)

fn getAngle A B =
(
	N1 = normalize A
	N2 = normalize B

	return (acos (dot N1 N2))

)

fn getMeshRadius pMesh =
(
	local nodeBound = nodeLocalBoundingBox  pMesh
	local nodeCenter = (nodeBound[1] + nodeBound[2]) * 0.5
		
	local w = nodeBound[2].x - nodeBound[1].x
	local d = nodeBound[2].z - nodeBound[1].z
	local t = nodeBound[2].y - nodeBound[1].y
	
	return ((getMax t (getMax w d)) * 0.5)
)

fn getMeshCenter pMesh =
(
	nodeBound = nodeLocalBoundingBox pMesh
	return ((nodeBound[1] + nodeBound[2]) * 0.5)
)

fn pickSplitPlane pMesh &rNormal &rOffset =
(
	c = getMeshCenter pMesh
	right = point3 0 0 0
	left = point3 0 0 0 
	normal = point3 0 0 0
	
	for i = 1 to pMesh.numVerts do
	(
		v = polyop.getVert pMesh i
		
		if v.x > c.x then
			right.x = right.x + 1
		else
			left.x = left.x + 1
		
		if v.y > c.y then
			right.y = right.y + 1
		else
			left.y = left.y + 1
		
		if v.z > c.z then
			right.z = right.z + 1
		else
			left.z = left.z + 1		
	)
	
	diff = point3 (abs (right.x - left.x)) (abs (right.y - left.y)) (abs (right.z - left.z))

	if diff.x > diff.y then
	(
		if diff.x > diff.z then
			normal = point3 1 0 0
		else (
			if diff.z > diff.y then (
				normal = point3 0 0 1
			)
			else
				normal = point3 0 1 0
		)
	)
	else
	(
		if diff.y > diff.z then
			normal = point3 0 1 0
		else (
			if diff.z > diff.x then
			(
				normal = point3 0 0 1
			)
			else
				normal = point3 1 0 0
		)
	)
	
	rNormal = normal
	rOffset = dot normal c
)

fn splitMesh pMesh &rLeftMesh &rRightMesh &rSplitNormal &rSplitOffset =
(
	nodeCenter = getMeshCenter pMesh
	
	local splitNormal = undefined
	local splitOffset = undefined
	pickSplitPlane pMesh &splitNormal &splitOffset
	
	local EA_x = getAngle splitNormal (point3 0 0 1) 
	local EA_z = getAngle splitNormal (point3 1 0 0)
	
	local splitEA = eulerAngles  0 EA_x EA_z 
	local splitRotation = (splitEA as quat)
	
	normalize splitRotation
	
	local posMesh = snapshot pMesh
		
	nodeBound = nodeLocalBoundingBox posMesh
	posSplitMod = sliceModifier()
	posSplitMod.Slice_Type = 2
	posSplitMod.slice_plane.controller[1].controller.value = ((nodeBound[1] + nodeBound[2]) * 0.5)
	posSplitMod.slice_plane.controller[2].controller.value = splitRotation
	addModifier posMesh posSplitMod
	centerpivot posMesh

	
	local negMesh = snapshot pMesh
	
	nodeBound = nodeLocalBoundingBox  negMesh
	negSplitMod = sliceModifier ()
	negSplitMod.Slice_Type = 3
	negSplitMod.slice_plane.position = ((nodeBound[1] + nodeBound[2]) * 0.5)
	negSplitMod.slice_plane.controller[1].controller.value = ((nodeBound[1] + nodeBound[2]) * 0.5)
	negSplitMod.slice_plane.controller[2].controller.value = splitRotation
	addModifier negMesh negSplitMod
	centerpivot negMesh
	
	rSplitNormal =splitNormal
	rSplitOffset = splitOffset
	rLeftMesh = negMesh
	rRightMesh = posMesh
)

struct treeNode (ID, leftChild, rightChild, isLeaf, leafData, splitNormal, splitOffset, radius, center)
--*********************************************************************
--*  Preforms subdivide recusion of the world
--*  
fn recurseSubdivide pMesh  treeDepth parentNode =
(
	local thisNodeID = gNodeCount
	gNodeCount = gNodeCount + 1
	
	if(gVerboseOutput)then
	(
		print "---------------------------------------"
		print "Split Decision:"
		print ("\tMesh faces:" + (pMesh.numFaces as string))
		print ("\tTree depth:" + (treeDepth as string))
		print ("\tMax depth:" + (gMaxDepth as string))
		print "---------------------------------------"
	) 
	
	if((pMesh.numFaces > gMaxTriangles) and (treeDepth < gMaxDepth)) then
	(
		
		local leftMesh = undefined
		local rightMesh = undefined
		local splitNormal = undefined
		local splitOffset = 0.0
		
		
		splitMesh pMesh &leftMesh &rightMesh &splitNormal &splitOffset
				
		if (leftMesh.numFaces == 0) then 
		(
			MessageBox "Warning"
			copy pMesh
		)
		
		if (rightMesh.numFaces == 0) then 
		(
			MessageBox "Warning"
			copy pMesh
		)
		parentNode.ID = thisNodeID
		parentNode.leafData = undefined
		parentNode.isLeaf = false
		parentNode.leftChild = treeNode -1 undefined undefined false undefined undefined undefined
		parentNode.rightChild = treeNode -1 undefined undefined false undefined undefined undefined
		parentNode.splitNormal = splitNormal
		parentNode.splitOffset = splitOffset
		parentNode.radius = (getMeshRadius pMesh)
		parentNode.center = (getMeshCenter pMesh)
		

		
		recurseSubdivide leftMesh (treeDepth + 1) parentNode.leftChild
		recurseSubdivide rightMesh (treeDepth + 1) parentNode.rightChild
	
			delete leftMesh
			delete rightMesh
		
	)
	else
	(
	
		if(gVerboseOutput) then
		(
			print "Write Leaf"
			print ("\This node: " + (gNodeCount as string))
			
		)
		
		local leafMesh = converttomesh ( snapshot pMesh )
	
		local nodeBound = nodeLocalBoundingBox  pMesh
		local nodeCenter = (nodeBound[1] + nodeBound[2]) * 0.5
		
		local nodeWide = nodeBound[2].x - nodeBound[1].x
		local nodeDeep = nodeBound[2].z - nodeBound[1].z
		local nodeTall = nodeBound[2].y - nodeBound[1].y
		
		local maxExtent = getMax nodeTall (getMax nodeWide nodeDeep)
		
		parentNode.ID = thisNodeID
		parentNode.leafData = leafMesh
		parentNode.isLeaf = true
		parentNode.leftChild = undefined
		parentNode.rightChild = undefined
		parentNode.splitNormal= undefined
		parentNode.splitOffset = undefined
		--parentNode.boundPoints = undefined
		parentNode.radius = undefined
		parentNode.center = undefined
		
	)
)

--*********************************************************************
--*  Preforms subdivide recusion of the world
--*  
fn recurseWrite pParentNode =
(
	if(pParentNode.isLeaf == true) then
	(
		if(gVerboseOutput) then
		(
			print "Write Leaf"
			print ("ID: " + (pParentNode.ID as string))
		)
		
		/*Write out the data for this node*/
		writeshort gFilestream -1	--signifies that this node is not an inner node
		writeshort gFilestream pParentNode.ID
		--Write bounds data
		
		local nodeMesh = pParentNode.leafData
		if(isNodeMeshType nodeMesh) then
		(
			exportMesh nodeMesh nodeMesh.material
		)
		
		totaLeavesWritten = totaLeavesWritten + 1
		nodeMesh.name = (pParentNode.ID as string)
		
		if(gBSPCleanup) do	
			delete nodeMesh
	)
	else
	(
		if(gVerboseOutput) then
		(
			print "Write Innernode"
			print ("ID: " + (pParentNode.ID as string))
			print ("ID (left-child): " + (pParentNode.leftChild.ID as string))
			print ("ID (right-child): " + (pParentNode.rightChild.ID as string))
			print ("Split plane: " + (pParentNode.splitNormal as string) + " " + (pParentNode.splitOffset as string))
		)
		
		/*Write out the data for this node*/
		writeshort gFilestream -2	--signifies that this node is an inner node
		writeshort gFilestream pParentNode.ID
		--Write the child ids
		writeshort gFilestream (pParentNode.leftChild.ID)
		writeshort gFilestream (pParentNode.rightChild.ID)
		--Write the split plane data
		writefloat gFilestream pParentNode.splitOffset
		WriteVector pParentNode.splitNormal
		
		writefloat gFilestream pParentNode.radius
		WriteVector pParentNode.center
		
		recurseWrite pParentNode.leftChild
		recurseWrite pParentNode.rightChild
		
		totalInnerNodesWritten = totalInnerNodesWritten + 1
	)
	
)



--*********************************************************************
--*  Compiles the world to a level for the engines file format
--*  
fn compileWorldNode pNode = 
(
	gNodeCount = 0
	gRoot = treeNode gNodeCount undefined undefined false undefined undefined undefined 
 
	
	if ((gExportBakedCoordinates == true) and ((polyop.getNumMaps pNode) > 1)) then
	(
		exportAmbientOcclusion pNode 
		writeFileStr ((pNode.name as string) + "_ao_map.jpg")
	)
	else
		writeFileStr (undefined)
	
	
	print "****************************************"
	print "Beginning subdivision..."
	print "****************************************"

	recurseSubdivide pNode 0 gRoot 
	
	print "****************************************"
	print "Subdivision complete. Tree constructed."
	print "Now continuing to write file..."
	print "****************************************"
		
	writeshort gFilestream gNodeCount
	recurseWrite gRoot
	
	print "****************************************"
	print "File written"
	print ("Total Inner Nodes:\t " + (totalInnerNodesWritten as string))
	print ("Total Leaves:\t " + (totaLeavesWritten as string))
	print "****************************************"
	
	totalInnerNodesWritten = 0
	totaLeavesWritten = 0
	
)


--*********************************************************************
--*  Compiles the world to a level for the engines file format
--*  
fn compileWorld = 
(
	local pWorldNode = undefined;
	for obj in objects do
	(
		local objectType = obj.baseObject as string
		if(isNodeMeshType obj and (obj.name == "level")) do
		(
			pWorldNode = obj
			break
		)
	)
	
	if(pWorldNode == undefined) do
	(
		messageBox "No level in scene. Make sure a mesh exsists with name 'level'"
		return 0;
	)
		
	openOutputFile (gWorldFilename +  ".wld")
	writeshort gFilestream 201
	
	compileWorldNode pWorldNode
	
	local pLevelObjects = #();
	
	for obj in objects do
	(
		if(pWorldNode == obj) do
		continue
		
		if(isNodeType "XRef Object" obj) do
		(
			append pLevelObjects obj
		)
	)

	local objectCount = 0
	if(gWriteObjects) then
		objectCount = pLevelObjects.count
	
	if (writeshort gFilestream objectCount) == false do
		print "error"

	if(gWriteObjects) then
	(
		for obj in pLevelObjects do
		(
			local objectName = (getFilenameFile obj.fileName) as string
			writeFileStr objectName
			WriteMatrix	(obj.transform as matrix3)
		)
	)
	
	writeshort gFilestream 201
	print "closing physics file"
	closeOutputFile()
	
					
)
